맨위로가기

이론 컴퓨터 과학

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

이론 컴퓨터 과학은 계산, 자료 구조, 알고리즘, 프로그래밍 언어, 정보 이론 등 컴퓨터 과학의 수학적 기초를 연구하는 분야이다. 1930년대 괴델의 불완전성 정리와 튜링, 처치 등의 알고리즘 정의를 통해 발전했으며, 20세기 후반 정보 이론, 계산 복잡도 이론, 양자 컴퓨팅 등의 분야가 등장했다. 주요 분야로는 알고리즘, 자료 구조, 계산 복잡도 이론, 프로그래밍 언어 이론, 정보 이론, 오토마타 이론, 부호 이론, 계산 기하학, 계산적 수론, 암호학, 분산 컴퓨팅, 병렬 컴퓨팅, 기계 학습, 자연 컴퓨팅, 양자 컴퓨팅, 기호적 계산 등이 있으며, 관련 학회 및 기관으로 ACM SIGACT, 유럽 이론 컴퓨터 과학 협회 등이 있다.

더 읽어볼만한 페이지

  • 이론 컴퓨터 과학 - 알고리즘
    알고리즘은 문제 해결을 위한 명확하고 순서화된 유한 개의 규칙 집합으로, 알콰리즈미의 이름에서 유래되었으며, 수학 문제 해결 절차로 사용되다가 컴퓨터 과학에서 중요한 역할을 하며 다양한 방식으로 표현되고 효율성 분석을 통해 평가된다.
  • 이론 컴퓨터 과학 - 자동화된 추론
    자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.
  • 형식과학 - 통계학
    통계학은 데이터를 수집, 분석, 해석하여 추론과 예측을 수행하는 학문으로, 기술 통계와 추론 통계를 통해 데이터를 요약, 설명하고 모집단의 특성을 추론하며, 다양한 분야에서 의사결정 도구로 활용된다.
  • 형식과학 - 컴퓨터 과학
    컴퓨터 과학은 컴퓨터와 관련된 현상을 연구하는 학문으로, 계산 이론, 하드웨어 및 소프트웨어 설계, 문제 해결 등을 포괄하며, 수학, 공학 등 여러 분야와 융합하여 발전해 왔다.
이론 컴퓨터 과학
이론 전산학
분야전산학 및 수학의 하위 분야
연구 분야알고리즘
자료 구조
계산 복잡도
병렬 및 분산 컴퓨팅
확률적 컴퓨팅
양자 컴퓨팅
오토마타 이론
정보 이론
암호학
프로그램 의미론 및 검증
알고리즘 게임 이론
기계 학습
계산 생물학
계산 경제학
계산 기하학
계산 정수론 및 대수학
학문적 접근
강조점수학적 기법과 엄밀성

2. 역사

알고리즘은 유클리드 호제법[58][59]처럼 수천 년 전부터 존재했지만, 계산에서의 알고리즘 정의를 정식화한 것은 1938년 앨런 튜링, 알론조 처치, 스티븐 클리니였다.

현대 이론 컴퓨터 과학 연구는 이러한 기본적인 발전을 기반으로 하지만, 아래 표와 같이 제기된 다른 많은 수학적 및 학제 간 문제를 포함한다.

수리 논리학오토마타 이론정수론그래프 이론계산 가능성 이론계산 복잡도 이론
P \rightarrow Q \,
오토마타
타원 곡선
그래프
왕 타일
P = NP ?
암호학타입 이론범주론계산 기하학조합 최적화양자 컴퓨팅 이론
GNITIRW-TERCES\Gamma\vdash x: \text{Int}
가환 다이어그램
단순 영역 탐색
독일 순회 판매원 문제
블로흐 구


2. 1. 수학 및 논리학의 발전

논리학적 추론과 수학적 증명은 이전부터 존재했지만, 1931년 쿠르트 괴델은 불완전성 정리를 통해 증명하거나 반증할 수 있는 명제에 근본적인 한계가 있음을 증명했다.[61][62][63]

이진법과 수학의 형식 체계는 그 이전부터 존재했으며, 고트프리트 빌헬름 라이프니츠가 17세기에 이진법을 수학적으로 정식화했고, 19세기에 조지 부울이 부울 논리를 정식화했다.[60]

2. 2. 계산 이론의 등장

1938년 앨런 튜링, 알론조 처치, 스티븐 클리니는 계산에서의 알고리즘 정의를 정식화했다.[60] 이들의 연구는 논리학과 계산 가능성에 대한 현대적 연구를 이끌었으며, 이는 이론 컴퓨터 과학 분야의 탄생으로 이어졌다.

1931년 쿠르트 괴델은 불완전성 정리를 통해 공리 체계에는 증명할 수 없는 한계가 존재함을 증명했다.[61][62][63]

1948년 클로드 섀넌은 통신의 수학적 이론을 발표하여 정보 이론을 확립했다.[64][65][66] 같은 시기 도널드 헤브는 뇌의 학습을 수학적으로 모델링한 헤브의 법칙을 제시했다. 이는 신경망과 병렬 분산 처리 연구의 기초가 되었다.

1971년 스티븐 쿡과 레오니드 레빈은 독립적 발견을 통해 NP-완전 문제의 존재를 증명하여 계산 복잡도 이론 발전에 기여했다.[2]

20세기 후반에는 양자 컴퓨터 개념이 등장했고, 1990년대 피터 쇼어는 양자 컴퓨터를 이용한 다항 시간 소인수 분해 알고리즘을 제시하여 공개 키 암호 시스템의 안전성에 대한 논의를 촉발시켰다.[67][68][69][70]

2. 3. 양자 컴퓨팅의 등장

20세기 초 양자역학의 발전은 양자의 파동 함수 위에서 연산을 수행하는 개념을 제시하였다. 이는 여러 상태를 동시에 병렬적으로 계산할 수 있음을 의미한다. 20세기 후반, 양자 컴퓨터 개념이 등장했고, 1990년대에는 피터 쇼어가 양자 컴퓨터를 사용하여 소인수 분해를 다항 시간 안에 해결할 수 있음을 보였다. 이는 만약 실현된다면 공개 키 암호 시스템의 안전성에 큰 영향을 줄 수 있음을 시사했다.[67][68][69][70]

3. 주요 분야

이론 컴퓨터 과학은 컴퓨터 과학의 한 분야로, 계산의 본질과 한계를 수학적, 논리적으로 연구한다. ACM 알고리즘 및 계산 이론 특별 이익 그룹(SIGACT)에 따르면, 이론 컴퓨터 과학은 알고리즘, 자료 구조, 계산 복잡도 이론, 병렬 계산, 분산 컴퓨팅, 확률적 계산, 양자 계산, 오토마타 이론, 정보 이론, 암호 이론, 프로그램 의미론과 검증, 기계 학습, 계산 생물학, 계산 경제학, 계산 기하학, 계산적 정수론 및 대수학 등을 포함한다.[55] ACM의 학술지 Transactions on Computation Theory는 여기에 부호 이론과 계산적 학습 이론을 추가하고, 데이터베이스, 정보 검색, 경제 모델, 네트워크 등의 이론 컴퓨터 과학적 측면도 포함한다.[56]

이론 컴퓨터 과학은 응용 분야와는 다르게 "컴퓨팅을 지탱하는 (보다 기본적인) 과학"을 연구한다는 인식이 있다.[57] 그러나 이는 대립이 아닌 협력 관계를 의미한다.

이론 컴퓨터 과학의 주요 분야
분야설명이미지
수리 논리학P\rightarrow Q
오토마타자동화된 계산 과정을 연구한다.
수론--
그래프 이론
형식 이론\Gamma \vdash x:Int
범주론--
계산 기하학기하학적 문제 해결 알고리즘을 연구한다.
심플렉스 범위 탐색
양자 계산양자 컴퓨터는 양자역학적 현상을 이용하여 계산을 수행한다.


3. 1. 알고리즘

알고리즘은 계산, 데이터 처리, 자동화된 추론 등 계산을 위한 단계별 절차이다.[3] 함수 계산을 위해 잘 정의된 명령어[4] 집합을 유한 목록[3]으로 표현한 효율적인 방법으로 사용된다.[5] 초기 상태와 초기 입력(아마도 빈 문자열)[6]에서 시작하여, 명령어는 계산을 설명하며, 실행될 때 유한[7] 수의 잘 정의된 연속적인 상태를 거쳐 결국 "출력"[8]을 생성하고 최종 종료 상태에서 종료된다. 한 상태에서 다음 상태로의 전환은 반드시 결정론적일 필요는 없으며, 랜덤 알고리즘으로 알려진 일부 알고리즘은 임의의 입력을 통합한다.[9]

알고리즘은 수천 년 전부터 존재했지만(예: 두 수의 최대공약수를 구하는 유클리드 호제법은 지금도 사용되고 있다.[58][59]), 계산에서의 알고리즘 정의를 정식화한 것은 앨런 튜링, 앨론조 처치, 스티븐 클리니로, 1938년의 일이다.

3. 2. 자료 구조

자료 구조는 컴퓨터에서 자료를 효율적으로 사용할 수 있도록 구성하는 특정 방법이다.[13][14]

다양한 종류의 자료 구조는 다양한 종류의 응용 프로그램에 적합하며, 일부는 특정 작업에 매우 특화되어 있다. 예를 들어, 데이터베이스는 적은 양의 데이터 검색에 B-트리 인덱스를 사용하고, 컴파일러와 데이터베이스는 동적 해시 테이블을 조회 테이블로 사용한다.

자료 구조는 대규모 데이터베이스 및 인터넷 인덱싱 서비스와 같은 용도로 많은 양의 데이터를 효율적으로 관리하는 수단을 제공한다. 일반적으로 효율적인 자료 구조는 효율적인 알고리즘 설계를 위한 핵심이다. 일부 공식 설계 방법론과 프로그래밍 언어는 소프트웨어 설계의 핵심 구성 요소로 알고리즘보다는 자료 구조를 강조한다. 저장 및 검색은 주 기억 장치와 보조 기억 장치에 모두 저장된 데이터에서 수행될 수 있다.

3. 3. 계산 복잡도 이론

계산 복잡도 이론은 계산 이론의 한 분야로, 계산 문제를 본질적인 어려움에 따라 분류하고 해당 종류 간의 관계를 연구한다. 계산 문제는 원칙적으로 컴퓨터로 해결할 수 있는 작업, 즉 알고리즘과 같이 수학적 단계를 기계적으로 적용하여 문제를 해결할 수 있다는 의미로 이해된다.

문제 해결에 사용된 알고리즘에 관계없이 상당한 자원이 필요하다면, 그 문제는 본질적으로 어렵다고 간주된다. 이 이론은 이러한 직관을 공식화하여, 수학적 계산 모델을 도입하여 이러한 문제를 연구하고, 시간과 저장 공간과 같이 문제를 해결하는 데 필요한 자원의 양을 정량화한다. 또한 통신 복잡도에서 사용되는 통신량, 회로 복잡도에서 사용되는 회로의 논리 게이트 수, 그리고 병렬 컴퓨팅에서 사용되는 프로세서의 수와 같은 다른 복잡성 척도도 사용된다. 계산 복잡도 이론의 역할 중 하나는 컴퓨터가 할 수 있고 할 수 없는 것에 대한 실제적인 한계를 결정하는 것이다.

정확한 연구 범위를 언급하는 것은 쉽지 않지만, ACM의 SIGACT는 이 그룹의 목적을 이론 컴퓨터 과학의 진흥으로 하고 있으며, 그 대상 범위를 다음과 같이 정의하고 있다[55]。

ACM의 학술지 Transactions on Computation Theory에서는 이 목록에 더하여 부호 이론과 계산적 학습 이론을 추가하고, 데이터베이스, 정보 검색, 경제 모델, 네트워크 등의 이론 컴퓨터 과학적 측면도 포함하고 있다[56]。이처럼 범위는 넓지만, 컴퓨터 과학의 이론 분야에 종사하는 사람들은 응용 분야와는 다르다는 인식을 가지고 있으며, "컴퓨팅을 지탱하는 (보다 기본적인) 과학"을 연구하고 있다는 인식을 가지고 있는 경우가 있다[57]。이것은 반드시 대립을 의미하는 것이 아니라, 오히려 협력 관계에 있음을 의미한다.

3. 4. 프로그래밍 언어 이론 및 프로그램 의미론

프로그래밍 언어 이론은 프로그래밍 언어와 개별적인 기능의 설계, 구현, 분석, 특성화 및 분류를 다루는 컴퓨터 과학의 한 분야이다. 이는 이론 컴퓨터 과학의 분야에 속하며, 수학, 소프트웨어 공학, 언어학에 의존하고 영향을 미친다. 프로그래밍 언어 이론은 수많은 전문 학술 저널이 존재하는 활발한 연구 분야이다.[19]

프로그래밍 언어 이론에서 '''의미론'''은 프로그래밍 언어의 의미에 대한 엄격한 수학적 연구를 다루는 분야이다. 이는 특정 프로그래밍 언어에 의해 정의된 구문론적으로 유효한 문자열의 의미를 평가하여, 관련된 계산을 보여준다. 의미론은 특정 언어로 프로그램을 실행할 때 컴퓨터가 따르는 프로세스를 설명한다. 이는 프로그램의 입력과 출력 간의 관계를 설명하거나, 특정 컴퓨터 플랫폼에서 프로그램이 어떻게 실행될지에 대한 설명을 통해 보여줄 수 있으며, 따라서 계산 모델을 생성한다.[19]

형식 기법은 수학 기반 기술의 일종으로, 형식 명세를 통해 소프트웨어 및 컴퓨터 하드웨어 시스템의 개발 및 형식 검증을 수행하는 데 사용된다.[17] 다른 공학 분야와 마찬가지로 적절한 수학적 분석을 수행하면 설계의 신뢰성과 견고성에 기여할 수 있다는 기대에 따라 소프트웨어 및 하드웨어 설계를 위해 형식 기법을 사용한다.[18] 형식 기법은 광범위한 다양한 이론 전산학의 기본 원리를 적용하는 것으로, 논리 계산, 형식 언어, 오토마타 이론, 프로그램 의미론 뿐만 아니라 타입 시스템과 대수적 데이터 타입을 소프트웨어 및 하드웨어 명세 및 검증 문제에 적용한다.[19]

3. 5. 정보 이론

정보 이론은 응용 수학, 전기 공학, 컴퓨터 과학의 한 분야로, 정보의 계량화를 다룬다. 클로드 섀넌에 의해 개발되었으며, 데이터 압축과 같이 신호 처리 작업의 근본적인 한계를 찾고 데이터를 안정적으로 저장하고 통신하는 것을 목표로 한다.[20] 이후 통계적 추론, 자연어 처리, 암호학, 신경생물학, 분자 코드의 진화[21] 및 기능[22], 통계학의 모델 선택[23], 열 물리학[24], 양자 컴퓨팅, 언어학, 표절 탐지[25], 패턴 인식, 이상 감지 및 기타 형태의 데이터 분석을 포함한 많은 다른 분야로 확산되었다.[26]

정보 이론의 기본적인 주제의 응용 분야로는 무손실 데이터 압축 (예: ZIP 파일), 손실 데이터 압축 (예: MP3 및 JPEG), 채널 용량 (예: DSL) 등이 있다. 이 분야는 수학, 통계학, 컴퓨터 과학, 물리학, 신경생물학, 전기 공학의 교차점에 있다. 정보 이론의 영향은 보이저 심우주 탐사, 콤팩트 디스크의 발명, 휴대 전화의 실현 가능성, 인터넷의 개발, 언어학과 인간 지각에 대한 연구, 블랙홀의 이해, 그리고 수많은 다른 분야에서 매우 중요했다. 정보 이론의 중요한 하위 분야는 소스 코딩, 채널 코딩, 알고리즘 복잡성 이론, 알고리즘 정보 이론, 정보 이론적 보안, 정보의 척도 등이 있다.

3. 6. 오토마타 이론

오토마타 이론은 추상 기계와 오토마타는 물론, 이를 사용하여 해결할 수 있는 계산 문제를 연구하는 분야이다. 이산 수학, 수학 및 컴퓨터 과학의 한 분야인 이론 컴퓨터 과학의 한 분야이기도 하다. ''오토마타(Automata)''는 "자동으로 작동하는"을 의미하는 그리스어 αὐτόματα에서 유래되었다.

오토마타 이론은 입력 및 출력 과정의 논리적 이해를 돕기 위해 자기 작동 가상 머신을 연구하며, 계산(또는 모든 함수/프로세스)의 중간 단계 유무와 관계없이 모든 경우를 포함한다.[55]

ACM의 알고리즘 및 계산 이론 특별 이익 그룹(SIGACT)은 이론 컴퓨터 과학의 진흥을 목적으로 하며, 그 대상 범위를 다음과 같이 정의하고 있다.[55]

관련 학문 분야
알고리즘
자료 구조
계산 복잡성 이론
병렬 계산
분산 계산
확률적 계산
양자 계산
오토마타 이론
정보 이론
암호 이론
프로그램 의미론과 검증
기계 학습
계산 생물학
계산 경제학
계산 기하학
계산적 정수론 및 대수학
수리 논리학
수론
그래프 이론
형식 이론
범주론



ACM의 학술지 Transactions on Computation Theory에서는 위에 더하여 부호 이론과 computational learning theory|계산적 학습 이론영어을 추가하고, 데이터베이스, 정보 검색, 경제 모델, 네트워크 등의 이론 컴퓨터 과학적 측면도 포함하고 있다.[56]

이처럼 범위는 넓지만, 컴퓨터 과학의 이론 분야에 종사하는 사람들은 응용 분야와는 다르다는 인식을 가지고 있으며, "컴퓨팅을 지탱하는 (보다 기본적인) 과학"을 연구하고 있다는 인식을 가지고 있는 경우가 있다.[57] 이것은 반드시 대립을 의미하는 것이 아니라, 오히려 협력 관계에 있음을 의미한다.

3. 7. 부호 이론 (코드 이론)

부호 이론은 부호의 속성과 특정 응용 분야에 대한 적합성을 연구하는 학문이다. 부호는 데이터 압축, 암호학, 오류 정정, 그리고 더 최근에는 네트워크 코딩에도 사용된다. 부호는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하기 위해 정보 이론, 전기 공학, 수학, 컴퓨터 과학 등 다양한 과학 분야에서 연구된다. 이는 일반적으로 중복성을 제거하고 전송된 데이터의 오류를 수정(또는 감지)하는 것을 포함한다.[55]

3. 8. 계산 기하학



계산 기하학은 기하학적인 문제를 해결하기 위한 알고리즘을 연구하는 분야이다. 컴퓨터 그래픽스, CAD/CAM, 로봇 공학, 지리 정보 시스템 등 다양한 분야에 응용된다.[55]

3. 9. 계산적 수론

계산적 수론은 '''알고리즘적 수론'''이라고도 하며, 수론적 계산을 수행하기 위한 알고리즘에 대한 연구이다. 이 분야에서 가장 잘 알려진 문제는 정수 인수분해이다.[55]

3. 10. 암호학

암호학은 제3자(적대자)가 있는 상황에서 안전한 통신을 위한 기술을 연구하고 실천하는 것이다.[10] 더 일반적으로, 적대자의 영향을 극복하는 통신 프로토콜을 구축하고 분석하는 것에 관한 것이며, 데이터 기밀성, 데이터 무결성, 인증, 부인 방지 등 정보 보안의 다양한 측면과 관련이 있다.[12] 현대 암호학은 수학, 컴퓨터 과학, 전기 공학의 학문 분야와 교차한다. 암호학의 응용 분야로는 ATM 카드, 컴퓨터 비밀번호, 전자 상거래 등이 있다.

현대 암호학은 수학 이론과 컴퓨터 과학 실천에 크게 기반을 두고 있다. 암호 알고리즘은 계산 복잡도 가정을 기반으로 설계되어, 실제로 어떤 적대자도 이러한 알고리즘을 깨뜨리기 어렵게 만든다. 이론적으로는 이러한 시스템을 깨뜨리는 것이 가능하지만, 알려진 실용적인 수단으로는 그렇게 하는 것이 불가능하다. 따라서 이러한 방식은 계산상 안전하다고 일컬어진다. 예를 들어 정수 인수분해 알고리즘의 개선과 더 빠른 컴퓨팅 기술과 같은 이론적 진보는 이러한 솔루션을 지속적으로 적용해야 할 필요성을 제기한다. 무제한의 컴퓨팅 성능으로도 깨뜨릴 수 없다는 것을 의미하는 정보 이론적 보안 방식도 존재한다. 예를 들어 일회용 패드가 있으며, 이러한 방식은 이론적으로는 깨질 수 있지만 계산상 안전한 메커니즘보다 구현하기 어렵다.

3. 11. 분산 컴퓨팅

분산 컴퓨팅은 컴퓨터 네트워크에 위치한 구성 요소가 메시지 전달을 통해 통신하고 작업을 조정하는 소프트웨어 시스템인 분산 시스템을 연구하는 분야이다.[15] 분산 시스템의 구성 요소들은 공통 목표를 달성하기 위해 서로 상호 작용한다. 분산 시스템의 세 가지 중요한 특징은 구성 요소의 동시성, 글로벌 시계 부재, 구성 요소의 독립적인 장애이다.[15] 분산 시스템의 예로는 서비스 지향 아키텍처 기반 시스템에서 대규모 다중 사용자 온라인 게임, 피어 투 피어 애플리케이션, 비트코인과 같은 블록체인 네트워크에 이르기까지 다양하다.

분산 시스템에서 실행되는 컴퓨터 프로그램을 '''분산 프로그램'''이라고 하며, 분산 프로그래밍은 이러한 프로그램을 작성하는 과정이다.[16] 원격 프로시저 호출과 유사한 커넥터 및 메시지 지향 미들웨어를 포함하여 메시지 전달 메커니즘에는 여러 가지 대안이 있다. 분산 시스템의 중요한 목표이자 과제는 위치 투명성이다.

3. 12. 병렬 컴퓨팅

병렬 컴퓨팅은 여러 계산을 동시에 수행하는 컴퓨팅 형태이다.[33] 큰 문제를 더 작은 문제로 나누어 병렬로 해결하는 원리에 기반한다. 병렬 컴퓨팅에는 비트 수준, 명령어 수준, 데이터, 태스크 병렬 처리 등 여러 형태가 있다.

병렬 처리는 오랫동안 고성능 컴퓨팅에 사용되었지만, 주파수 스케일링을 방해하는 물리적 제약 때문에 최근 더 주목받고 있다.[34] 컴퓨터의 전력 소비와 열 발생이 문제가 되면서, 병렬 컴퓨팅은 주로 멀티 코어 프로세서 형태로 컴퓨터 아키텍처의 주요 패러다임이 되었다.[35][36]

병렬 컴퓨터 프로그램은 순차 프로그램보다 작성하기 어렵다.[37] 동시성은 여러 종류의 잠재적인 소프트웨어 버그를 발생시키며, 그중 경쟁 조건이 가장 흔하다. 서로 다른 하위 작업 간의 통신 및 동기화는 좋은 병렬 프로그램 성능을 얻는 데 큰 장애물이다.

단일 프로그램의 최대 가능한 속도 향상은 암달의 법칙으로 알려져 있다.

3. 13. 기계 학습

기계 학습은 데이터로부터 학습할 수 있는 알고리즘의 구축과 연구를 다루는 학문 분야이다.[27] 이러한 알고리즘은 명시적으로 프로그래밍된 지침만을 따르는 대신, 입력을 기반으로 통계 모델을 구축하고 이를 사용하여 예측 또는 결정을 내림으로써 작동한다.[28]

기계 학습은 컴퓨터 과학과 통계학의 하위 분야로 간주될 수 있다. 기계 학습은 이 분야에 방법, 이론 및 응용 분야를 제공하는 인공 지능 및 수리 최적화와 강력한 연관성을 가진다. 기계 학습은 명시적이고 규칙 기반의 알고리즘을 설계하고 프로그래밍하는 것이 불가능한 광범위한 컴퓨팅 작업에 사용된다. 예를 들어, 스팸 필터링, 광학 문자 인식(OCR),[29] 검색 엔진 및 컴퓨터 비전 등이 있다. 기계 학습은 때때로 데이터 마이닝과 혼동되기도 하지만,[30] 데이터 마이닝은 탐색적 데이터 분석에 더 중점을 둔다.[31] 기계 학습과 패턴 인식은 "동일한 분야의 두 가지 측면으로 볼 수 있다."[28]

3. 14. 자연 컴퓨팅

ACM의 알고리즘 및 계산 이론 특별 이익 그룹(SIGACT)은 이론 컴퓨터 과학의 범위를 알고리즘, 자료 구조, 계산 복잡성 이론, 병렬 계산, 분산 계산, 확률적 계산, 양자 계산, 오토마타 이론, 정보 이론, 암호 이론, 프로그램 의미론과 검증, 기계 학습, 계산 생물학, 계산 경제학, 계산 기하학, 계산적 정수론 및 대수학으로 정의하고 있다.[55]

ACM의 학술지 Transactions on Computation Theory에서는 여기에 부호 이론과 계산적 학습 이론을 추가하고, 데이터베이스, 정보 검색, 경제 모델, 네트워크 등의 이론 컴퓨터 과학적 측면도 포함하고 있다.[56]

3. 15. 양자 컴퓨팅

양자 컴퓨터는 양자 중첩 및 양자 얽힘과 같은 양자역학적 현상을 직접 사용하여 데이터에 대한 연산을 수행하는 계산 시스템이다.[38] 양자 컴퓨터는 트랜지스터를 기반으로 하는 디지털 컴퓨터와 다르다. 디지털 컴퓨터는 데이터를 비트로 인코딩해야 하며, 각 비트는 항상 0 또는 1의 상태 중 하나에 있지만, 양자 계산은 여러 상태의 양자 중첩 상태에 있을 수 있는 큐비트(quantum bits)를 사용한다. 양자 튜링 기계는 양자 컴퓨터의 이론적 모델이며, 보편적인 양자 컴퓨터라고도 알려져 있다. 양자 컴퓨터는 비결정적 튜링 기계 및 확률적 오토마타와 이론적인 유사성을 공유하는데, 예를 들어 동시에 여러 상태에 있을 수 있다. 양자 컴퓨팅 분야는 1980년 유리 마닌[39]과 1982년 리처드 파인만에 의해 처음 소개되었다.[40][41] 1968년에는 양자 비트로서 스핀을 가진 양자 컴퓨터가 양자 시공간으로 사용하기 위해 공식화되었다.[42]

매우 적은 수의 큐비트에서 양자 계산 연산을 실행하는 실험이 수행되었다.[43] 실제 및 이론 연구가 계속 진행 중이며, 많은 국가 정부 및 군사 자금 지원 기관은 암호 해독과 같은 민간 및 국가 안보 목적으로 양자 컴퓨터를 개발하기 위해 양자 컴퓨팅 연구를 지원하고 있다.[44]

20세기 초 양자역학의 발전에 의해, 양자의 파동 함수 위에서 연산이 가능하지 않을까 하는 개념이 생겨났다. 이는 곧, 여러 상태를 동시 병렬적으로 계산할 수 있음을 의미한다. 20세기 후반에 양자 컴퓨터의 개념이 생겨났고, 1990년대에는 피터 쇼어가 양자 컴퓨터를 사용하면 소인수 분해를 다항 시간으로 풀 수 있음을 보여주었다. 만약 수천만 양자 비트를 양자적으로 다룰 수 있는 양자 컴퓨터가 실현된다면 공개 키 암호 시스템도 안전하지 않게 될 것이다.[67][68][69][70]

3. 16. 기호적 계산 (컴퓨터 대수)

컴퓨터 대수학은 기호적 계산 또는 대수적 계산이라고도 불리며, 알고리즘과 소프트웨어를 연구하고 개발하여 수학 표현식 및 기타 수학적 객체를 조작하는 과학 분야이다. 과학 컴퓨팅의 하위 분야여야 하지만, 과학 컴퓨팅은 일반적으로 근사 부동 소수점 숫자를 사용한 수치 계산을 기반으로 하는 반면, 기호적 계산은 어떠한 값도 주어지지 않은 변수가 포함된 표현식으로 ''정확한'' 계산을 강조하기 때문에 일반적으로 별개의 분야로 간주된다.[55]

기호적 계산을 수행하는 소프트웨어 응용 프로그램은 ''컴퓨터 대수학 시스템''이라고 하며, 여기서 ''시스템''이라는 용어는 수학적 데이터를 컴퓨터로 표현하는 방법, 사용자 프로그래밍 언어, 전용 메모리 관리자, 수학적 표현식의 입/출력을 위한 사용자 인터페이스, 표현식 단순화, 연쇄 법칙을 사용한 미분, 다항식 인수분해, 부정 적분 등과 같은 일반적인 연산을 수행하는 대규모 루틴 집합을 포함하는 주요 응용 프로그램의 복잡성을 암시한다.

3. 17. 초고밀도 집적 회로 (VLSI)

초고밀도 집적 회로(VLSI)는 수천 개의 트랜지스터를 단일 칩으로 결합하여 집적 회로(IC)를 만드는 과정이다. VLSI는 복잡한 반도체 및 통신 기술이 개발되던 1970년대에 시작되었다. 마이크로프로세서는 VLSI 장치이다. VLSI 기술이 도입되기 전에는 대부분의 IC가 수행할 수 있는 기능이 제한적이었다. 전자 회로는 CPU, ROM, RAM 및 기타 보조 로직으로 구성될 수 있었다. VLSI를 통해 IC 제조업체는 이러한 모든 회로를 하나의 칩에 추가할 수 있게 되었다.

4. 관련 기관 및 학회

한국에서는 한국정보과학회, 한국정보처리학회 등에서 이론 컴퓨터 과학 관련 연구를 지원하고 학술 활동을 주도하고 있다. 국제적으로는 ACM SIGACT, 유럽 이론 컴퓨터 과학 협회 등이 대표적인 이론 컴퓨터 과학 관련 기관이다. 주요 국제 학회로는 전산학 이론 심포지엄(STOC)[45], 컴퓨터 과학 기초 심포지엄(FOCS)[45], 이산 알고리즘 심포지엄(SODA)[45], 컴퓨터 과학 논리 심포지엄(LICS)[45] 등이 있다.

참조

[1] 웹사이트 SIGACT https://www.sigact.o[...] 2017-01-19
[2] 서적 Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 1971
[3] 서적 Theory of Recursive Functions and Effective Computability McGraw-Hill
[4] 문서
[5] 문서
[6] 문서 An algorithm has [[zero]] or more inputs, i.e., [[quantity|quantities]] which are given to it initially before the algorithm begins
[7] 문서 A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'
[8] 문서 An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs
[9] 문서
[10] 서적 Handbook of Theoretical Computer Science Elsevier
[11] 서적 Introduction to Modern Cryptography 2005-09-21
[12] 서적 Handbook of Applied Cryptography https://archive.org/[...] Taylor & Francis
[13] 문서 data structure http://xlinux.nist.g[...] National Institute of Standards and Technology 2004-12-15
[14] 문서 data structure http://www.britannic[...] Encyclopædia Britannica 2009
[15] 서적 Distributed Systems: Concepts and Design Addison-Wesley
[16] 서적 Distributed Systems – An Algorithmic Approach Chapman & Hall/CRC
[17] 웹사이트 What is Formal Methods? http://shemesh.larc.[...] 2001-08-06
[18] 웹사이트 Why Engineers Should Consider Formal Methods http://klabs.org/ric[...] 16th Digital Avionics Systems Conference (27–30 October 1997) 2006-11-16
[19] 문서 Monin, pp.3–4
[20] 서적 Spikes: Exploring the Neural Code The MIT press
[21] 간행물 Bayesian Inference of Phylogeny and Its Impact on Evolutionary Biology American Association for the Advancement of Science (AAAS) 2001-12-14
[22] 문서 Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan
[23] 문서 Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York)
[24] 간행물 Information Theory and Statistical Mechanics American Physical Society (APS) 1957-05-15
[25] 문서 Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories
[26] 웹사이트 Some background on why people in the empirical sciences may want to better understand the information-theoretic methods http://aicanderson2.[...] 2003-11-01
[27] 간행물 Glossary of terms https://ai.stanford.[...]
[28] 서적 Pattern Recognition and Machine Learning Springer
[29] 문서 Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging
[30] 학술 Data mining: machine learning, statistics, and databases IEEE Computer Society
[31] 간행물 Data Mining and Statistics: What's the connection?
[32] 서적 Current Trends in Theoretical Computer Science 2001
[33] 서적 Highly parallel computing http://dl.acm.org/ci[...] Benjamin/Cummings
[34] 웹사이트 S.V. Adve et al. (November 2008). Parallel Computing Research at Illinois: The UPCRC Agenda http://www.upcrc.ill[...] 2008-12-09
[35] 문서 [[Krste Asanović|Asanovic]] et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".
[36] 논문 The Landscape of Parallel Computing Research: A View from Berkeley http://www.eecs.berk[...] University of California, Berkeley 2006-12-18
[37] 서적 Computer organization and design : the hardware/software interface https://archive.org/[...] Kaufmann
[38] 간행물 Quantum Computing with Molecules http://cba.mit.edu/d[...]
[39] 서적 Vychislimoe i nevychislimoe http://publ.lib.ru/A[...] Sov.Radio 2013-03-04
[40] 학술지 Simulating physics with computers
[41] 학술지 Quantum computation 1992-01-06
[42] 서적 Fundamental Interactions at High Energy Gordon & Breach
[43] 웹사이트 New qubit control bodes well for future of quantum computing http://phys.org/news[...] 2014-10-26
[44] 웹사이트 Quantum Information Science and Technology Roadmap http://qist.lanl.gov[...]
[45] 웹사이트 2007 Australian Ranking of ICT Conferences http://www.core.edu.[...]
[46] 웹사이트 MFCS 2017 http://mfcs2017.cs.a[...] 2018-01-09
[47] 웹사이트 CSR 2018 https://logic.pdmi.r[...]
[48] 웹사이트 2007 Australian Ranking of ICT Conferences http://www.core.edu.[...]
[49] 웹사이트 SOFSEM webpage https://www.sofsem.c[...] 2024-09-03
[50] 웹사이트 FCT 2011 http://fct11.ifi.uio[...] 2013-06-03
[51] 문서 Texts in Theoretical Computer Science An EATCS Series
[52] 문서 Monographs in Theoretical Computer Science An EATCS Series
[53] 학술지 Observations about the development of theoretical computer science
[54] 서적 プログラム意味論 共立出版
[55] 웹사이트 SIGACT http://sigact.acm.or[...] 2013-07-13
[56] 웹사이트 ToCT http://toct.acm.org/[...] 2010-06-09
[57] 웹사이트 Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing http://www.research.[...] 2009-03-29
[58] 학술지 ユークリッド互除法に基づく狭義 2 元 BCH 符号の復号について
[59] 학술지 ユークリッド復号法を用いたリードソロモン符号の BCH 限界以上の復号
[60] 서적 Boolean algebra Courier Corporation
[61] 서적 There's something about Gödel: the complete guide to the incompleteness theorem John Wiley & Sons
[62] 서적 Gödel's incompleteness theorems Oxford University Press on Demand
[63] 서적 不完全性定理 共立出版
[64] 학술지 A mathematical theory of communication
[65] 학위논문 The essential message: Claude Shannon and the making of information theory Massachusetts Institute of Technology
[66] 학술지 Claude E. Shannon: The 50th anniversary of information theory
[67] 컨퍼런스 Algorithms for quantum computation: discrete logarithms and factoring IEEE 1994-11
[68] 컨퍼런스 Introduction to quantum algorithms 2002-05
[69] 학술지 An introduction to quantum computing for non-physicists
[70] 서적 An introduction to quantum computing algorithms Springer Science & Business Media


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com